package algorithms.evictpolicy;

import java.util.HashMap;
import java.util.Map;

public class Queue<K> {

    private int size;
    private int tail;
    private K[] queue;
    private Map<K, Integer> keyIndexMap = new HashMap<>();

    @SuppressWarnings("unchecked")
    public Queue(int size) {
        this.size = size;
        this.queue = (K[]) new Object[size];
    }

    K push(K k) {
        K hk = null;
        if (tail == size) {
            hk = shiftHead();
        }
        tail++;
        int index = tail - 1;
        queue[index] = k;
        keyIndexMap.put(k, index);

        return hk;
    }

    void remove(K k) {
        moveForward(k);
        keyIndexMap.remove(k);
        queue[--tail] = null;
    }

    K shiftHead() {
        K head = queue[0];
        keyIndexMap.remove(head);
        int end = tail -= 1;
        for (int i = 0; i < end; i++) {
            K ki1 = queue[i + 1];
            keyIndexMap.put(ki1, i);
            queue[i] = ki1;
        }
        return head;
    }

    void swapToTail(K k) {
        moveForward(k);
        queue[tail - 1] = k;
        keyIndexMap.put(k, tail - 1);

    }

    void moveForward(K k) {
        Integer index = keyIndexMap.get(k);
        for (int i = index; i < tail - 1; i++) {
            K ki1 = queue[i + 1];
            int i1 = keyIndexMap.get(ki1);
            keyIndexMap.put(k, i1);
            queue[i] = ki1;
        }
    }
}
